#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdint.h>
#include <limits>
#include <time.h>
#include <stdlib.h>

#define MAX_LEVEL  10

//  srand((int)time(0));


struct Node {
    Node() {
        memset(next, sizeof(Node*) * MAX_LEVEL, 0);
    }

    int value;
    Node* next[MAX_LEVEL];
};


class JumpList {
public:
    JumpList() {
        m_lv = 0;
        m_head = new Node();
        m_head->value = std::numeric_limits<int>::min();
    }

    Node* Search(int key) {
        Node* tmp = m_head;
        for (int i = m_lv; i >= 0; --i) {
            while (tmp->next[i] != NULL && tmp->next[i]->value < key) {
                tmp = tmp->next[i];
            }
            //tmp = tmp->next[i];
            if (tmp->next[i] && tmp->next[i]->value == key) return tmp->next[i];
        }

        return NULL;
    }

    int Rand() {
        int ret = 0;
        while (rand() % 2 && ret < MAX_LEVEL) {
            ++ret;
        }
        return ret;
    }

    void Insert(int key)
    {
        int lv = Rand();

        Node* n = new Node();
        n->value = key;
        Node* tmp = m_head;
        Node* update[MAX_LEVEL] = {0};
        for (int i = lv; i >= 0; --i) {
            while (tmp->next[i] && tmp->next[i]->value < key) {
                tmp = tmp->next[i];
            }

            n->next[i] = tmp->next[i];
            tmp->next[i] = n;
        }

        if (lv > m_lv) m_lv = lv;
    }

    void Delete(int key) {
        Node* cur = m_head;
        for (int i = m_lv; i >= 0; --i) {
            while (cur->next[i] && cur->next[i]->value < key) {
                //last = cur;
                cur = cur->next[i];
            }
            if (cur->next[i] && cur->next[i]->value == key)
            {
                cur->next[i] = cur->next[i]->next[i];
                if (i == m_lv) --m_lv;
            }
        }
    }

    void Print()
    {
        std::cout << "---------------------begin-------------------" << std::endl;
        for (int i = m_lv; i >= 0; --i) {
            Node* tmp = m_head;
            std::cout << "level:" << i << " " << tmp->value << " ";
            while(tmp->next[i]) {
                tmp = tmp->next[i];
                std::cout << tmp->value << " ";
            }

            std::cout << std::endl;
        }
        std::cout << "---------------------end-------------------" << std::endl;
    }

private:
    Node* m_head;
    uint32_t m_lv;
};

int main(int argc, const char **argv) {
    srand(time(NULL));
    JumpList l;
    l.Insert(5);
    l.Insert(4);
    l.Print();
    l.Insert(3);
    l.Insert(2);
    l.Print();
    l.Insert(1);
    l.Print();

    Node* tmp = l.Search(1);
    if (tmp) std::cout << tmp->value << std::endl;

    l.Delete(1);
    l.Print();

    return 0;
}
